package com.hao.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * TODO
 *
 * @author 97472
 * @version 1.0
 * @date 2021/4/28 13:49
 */
public class PolandNotation {
    public static void main(String[] args) {
        // (3+4)*5-6 -> 34+5*6-
        // String suffixExpression = "3 4 + 5 * 6 -";
        // 36-6*8+6/3-4 -> 36 6 8 * - 6 3 / + 4 -
//         String suffixExpression = "36 6 8 * - 6 3 / + 4 -";
        System.out.println(infixExpressionToSuffix("( 3 + 4 ) * 5 - 6"));
        System.out.println(calculate("( 3 + 4 ) * 5 - 6"));
    }

    /**
     *  计算中缀表达式
     * @param infixExpression
     * @return
     */
    public static Integer calculate(String infixExpression){
        String suffixExpression = infixExpressionToSuffix(infixExpression);
        return calculateSuffix(suffixExpression);
    }

    /**
     * 将中缀表达式转换为后缀表达式
     * @return
     */
    private static String infixExpressionToSuffix(String infixExpression){
        String[] chs = infixExpression.split(" ");
        List<String> list = Arrays.asList(chs);
        Stack<String> suffixStack = new Stack<>();
        Stack<String> operatorStack = new Stack<>();
        list.forEach(ele -> {
            // 判断元素是否是数字
            boolean isNum = ele.matches("\\d+");
            boolean isBracket = "(".equals(ele) || ")".equals(ele);
            if (isNum){
                suffixStack.push(ele);
            }else if (isBracket){
                if ("(".equals(ele)){
                    operatorStack.push(ele);
                }else {
                    while (true){
                        String operator = operatorStack.pop();
                        if ("(".equals(operator)) {
                            break;
                        }
                        suffixStack.push(operator);
                    }
                }
            }else {
                while (true){
                    if (operatorStack.isEmpty()){
                        operatorStack.push(ele);
                        break;
                    }else{
                        String peek = operatorStack.peek();
                        if ( "(".equals(peek)){
                            operatorStack.push(ele);
                            break;
                        }else {
                            boolean levelIsHigh = ("/".equals(ele) || "*".equals(ele))&&("+".equals(peek) || "-".equals(peek));
                            if (levelIsHigh){
                                operatorStack.push(ele);
                                break;
                            }else {
                                operatorStack.pop();
                                suffixStack.push(peek);
                            }
                        }
                    }
                }
            }
        });

        suffixStack.push(operatorStack.pop());
        list = new ArrayList<>();
        list.addAll(suffixStack);
        StringBuilder suffixExpressionBuilder = new StringBuilder();
        list.forEach(str ->{
            suffixExpressionBuilder.append(str + " ");
        });
        int suffixLength = suffixExpressionBuilder.length();
        if (suffixLength != 0){
            suffixExpressionBuilder.delete(suffixLength-1,suffixLength);
        }
        return suffixExpressionBuilder.toString();
    }
    /**
     *  计算后缀表达式
     * @param suffixExpression
     * @return
     */
    public static Integer calculateSuffix(String suffixExpression){
        // 将表达式中的每个单位分割
        String[] chs = suffixExpression.split(" ");
        // 转换为list容器
        List<String> list = Arrays.asList(chs);
        Stack<String> stack = new Stack();
        list.forEach(ele -> {
            // 判断元素是否是数字
            boolean isNum = ele.matches("\\d+");
            if (isNum){
                // 如果是数字就直接push到stack中
                stack.push(ele);
            }else {
                // 如果是运算符就弹出两个数进行运算，再将结果压入栈中
                Integer num2 = Integer.valueOf(stack.pop());
                Integer num1 = Integer.valueOf(stack.pop());
                Integer res = 0;
                switch (ele){
                    case "+":
                        res = num1 + num2;
                        break;
                    case "-":
                        res = num1 - num2;
                        break;
                    case "*":
                        res = num1 * num2;
                        break;
                    case "/":
                        res = num1 / num2;
                        break;
                    default:
                        throw new RuntimeException();
                }
                stack.push(String.valueOf(res));
            }
        });
        return Integer.valueOf(stack.pop());
    }
}
